There are many methods of converting object descriptions to pixels. All such methods are called “rendering”. Object descriptions may be presented in Page Description Languages (PDLs) such as PCL, Postscript or PDF, or may be passed to the renderer via some programming interface. In any case, the renderer receives objects, usually in drawing order (also referred to as priority or z-order). The renderer then converts the received objects into pixels, which are horizontally and vertically ordered color and/or transparency values that may be used to drive a printer engine or display. The pixels may be used as an image for other purposes such as storage.
When a computer application provides data to a device for printing and/or display, an intermediate description of the page is often given to the device driver software in a page description language, such as Postscript or PCL. Such languages provide descriptions of the objects to be rendered onto the page, rather than a raster image of the page to be printed. Equivalently, a set of descriptions of graphics objects may be provided in function calls to a graphics interface, such as the GDI in the Microsoft Windows™ operating system, or the X-11 in the Unix™ operating system. The page is typically rendered for printing and/or display by an object-based graphics system (or Raster Image Processor). Additionally, the rendered output can be stored as an image, and such images may be transferred to other systems.
Most of these object-based graphics systems utilize a large area of memory, known as a framestore or a page buffer, to hold a pixel-based image of the page or screen for subsequent printing and/or display. Typically, the outlines of the graphic objects are calculated, filled and written into the framestore in sequence.
For two-dimensional graphics, objects that appear in front of other objects are simply written into the framestore after the background objects. Foreground objects thus replace the background on a pixel by pixel basis. Higher priority graphic objects take precedence because they are drawn later than those of lower priority. This is commonly known to the art as “Painter's algorithm”. Objects are considered in priority order, from the rearmost object to the foremost object. The rearmost object has the lowest priority (or Z order), and the foremost object has the highest priority (Z order). Typically, each object is rasterized in scanline order and pixels are written to the framestore in sequential runs (pixel spans) along each scanline.
Some graphics interfaces allow a logical or arithmetic operation to be specified, the operation being performed between one or more graphics objects and the pixels already rendered in the framestore. In such cases, the principle remains the same in that objects (or groups of objects) are rasterized in scanline order. The result of the specified operation is calculated and written to the framestore in sequential runs along each scanline.
There are two problems with the Painter's algorithm. The first is that the technique requires fast random access to all of the pixels in the framestore. This is because each new object could affect any pixel in the framestore. For this reason, the framestore is normally kept in semiconductor random access memory (RAM). For high-resolution color printers the amount of RAM required can be very large, typically in excess of 100 Mbytes. Large amounts of RAM are relatively costly and are difficult to run at high speed. The second problem is that many pixels in the framestore are over-painted (re-rendered) by later objects, often many times. Painting these pixels with the earlier objects can result in considerable wasted computation effort and wasted memory bandwidth. The problems with the Painter's algorithm result in lower rendering performance.
One method for overcoming the large framestore problem is the use of “banding”. When band rendering is used, only part of the framestore exists in memory at any one time. All of the objects to be drawn are retained in an object list by the rendering application. The object list is considered in object order as in the Painter's algorithm, but the only pixel operations performed are those which fall within the part of the page intersected by the band. After all objects in the object list have been drawn, the band is complete and can be sent to the printer (or to intermediate storage) and the process repeats for the next band on the page. With this method, the bands are rendered in order, down the page.
There are some penalties with this technique, however. It is necessary to retain in a list all objects to be drawn on the page. It may also be necessary to reconsider the objects being drawn many times, possibly once for each band. As the number of bands increases, so too does the repetitious examination of the objects being rendered. Also, the technique of banding does not solve the problem of over-painting. In some implementations, the overhead of dividing the page into bands can also result in a performance penalty.
Some other graphic systems consider the image in scanline order. Again, all of the objects on the page are retained in a list, which can be an intermediate display list. On each scanline the objects which intersect the scanline are considered in priority order. For each object, spans of pixels between the intersection points where the object edges intersect the scanline are filled in a line store. This technique overcomes the large framestore problem, but however still suffers from the over-painting problem.
Other graphic systems utilize pixel-sequential rendering to overcome both the large framestore problem and the over-painting problem. In these systems, each pixel is generated in raster order. Again, all objects to be drawn are retained in a list. On each scanline, the edges of objects which intersect that scanline, are held in increasing x-order of their intersection with the scanline. These points of intersection, or edge crossings, are considered in turn, and are used to decide whether the associated object is being ‘activated’ or ‘de-activated’ by the edge. Potentially, there are many objects contributing to a page. However, only relatively few of those objects are present (“active”) on each individual pixel. A pixel-sequential renderer may keep an array of fields that tracks the activity of the objects. There is one activity field for each object painting operation that is of interest on the scanline. There is also a field to indicate operations that do not require previously generated data.
Between each pair of edges considered, the color data for each pixel which lies between the first edge and the second edge is generated by using a priority encoder on the activity flags to determine the operations required to generate the color. The method only performs the determined operations for the span of pixels between the two edges. In preparation for the next scanline, the coordinate of intersection of each edge is updated in accordance with the nature of each edge, and the edges are sorted into increasing order of intersection with that scanline. Any new edges are also merged into the list of edges.
Graphic systems which use pixel-sequential rendering have significant advantages in that there is no framestore or line store and no unnecessary over-painting. The object priorities are dealt with in constant order time by the priority encoder, rather than in order N time, where N is the number of priorities.
Australian Patent No. 744091, and counterpart U.S. Pat. No. 6,483,519, issued 19 Nov. 2002 to Long et al, disclose such a pixel-sequential rendering system. The system comprises a pixel-sequential rendering engine which is used in conjunction with driver software that receives graphical objects from an application program, a host computer system, and a downstream printer device. This system is capable of rendering graphical shapes, images and text, in color. The system operates by building and processing graphical objects (defined by edges, fills, levels and color operations), then producing color output one scanline at a time. For each scanline the engine processes each pixel in turn and considers the graphical objects that affect that pixel in order to determine the output for the pixel. The engine maintains a table of active fills (known as the fill table) and a table of active levels (known as the level table), which are used in the determination of those objects which make an active contribution to the current pixel.
However, the pixel-sequential renderer also has some problems. Object data which generates many closely-packed edge crossings, or which causes many active levels at one time, or which generates a large amount of fill table data, causes the pixel-sequential renderer to perform poorly. Sometimes generation of this type of problematic object data can be prevented during generation of the object data. But often applications produce PDLs or intermediate formats which contain problematic object data. In this case, the rendering system must accept the problematic object data, which in turn causes poor performance.